
#include <cassert>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <conio.h>
#include <tchar.h>
#include <vector>
#include <windows.h>
using namespace std;

typedef char CellValue;
const CellValue CellEmpty = 0;
// 1 - 8
const CellValue CellUnknown = 9;
const CellValue CellFlag = 10;
const CellValue CellExploded = 11;

template<typename T>
class Array2D
{
public:
    Array2D(void): width(0), height(0), buf(0), idx(0)
    { }
    Array2D(int w, int h)
        : width(0), height(0), buf(0), idx(0)
    { SetSize(w, h); }
    ~Array2D(void)
    {
        delete idx;
        delete buf;
    }
    void SetSize(int w, int h)
    {
        assert(w >= 0);
        assert(h >= 0);

        if (w != width || h != height)
        {
            width = w;
            height = h;
            delete buf;
            buf = new T[w * h]();
            delete idx;
            idx = new T*[h];
        }
        memset(buf, 0, w * h * sizeof(T));
        if (h > 0) idx[0] = buf;
        for (int i = 1; i < h; ++i)
        {
            idx[i] = idx[i - 1] + w;
        }
    }
    void Assign(const Array2D<T>& that, int x, int y, int w, int h)
    {
        assert(x + w <= that.Width());
        assert(y + h <= that.Height());
        SetSize(w, h);
        for (int i = 0; i < h; ++i)
        {
            for (int j = 0; j < w; ++j)
            {
                idx[i][j] = that.idx[y + i][x + j];
            }
        }
    }
    int Width(void) const {return width;}
    int Height(void) const {return height;}
    bool IsSame(const Array2D<T>& that, int x = 0, int y = 0) const
    {
        assert(x + width <= that.width);
        assert(y + height <= that.height);
        const size_t rowBytes = sizeof(T) * width;
        for (int i = 0; i < height; ++i)
        {
            if (memcmp(idx[i], that.idx[y + i] + x, rowBytes) != 0)
            {
                return false;
            }
        }
        return true;
    }
    T& operator()(int x, int y)
    {
        assert(x < width);
        assert(y < height);
        return idx[y][x];
    }
    const T& operator()(int x, int y)const
    {
        assert(x < width);
        assert(y < height);
        return idx[y][x];
    }
private:
    Array2D(const Array2D&);
    const Array2D& operator=(const Array2D&);

    int width, height;
    T* buf;
    T** idx;
};

typedef Array2D<CellValue> Field;
typedef Array2D<int> Image;

template<typename T, size_t BOUND>
class BoundArray
{
public:
    BoundArray(void):sz(0), arr()
    {}

    T& operator[](size_t i)
    {
        assert(i < sz);
        return arr[i];
    }
    const T& operator[](size_t i) const
    {
        assert(i < sz);
        return arr[i];
    }
    void add(const T& t)
    {
        assert(sz < BOUND);
        arr[sz++] = t;
    }
    int size(void) const
    { return (int)sz; }
    bool empty(void) const
    { return sz == 0; }
    void remove(bool (&rm)[BOUND])
    {
        int dist = 0;
        for (size_t i = 0; i < sz; ++i)
        {
            if (rm[i]) ++dist;
            else arr[i - dist] = arr[i];
        }
        sz -= dist;
    }
private:
    T arr[BOUND];
    size_t sz;
};

void GetImage(HBITMAP bitmap, Image& image)
{
    BITMAP bm;
    BOOL ret = GetObject(bitmap, sizeof(bm), &bm);
    assert(ret);
    assert(bm.bmBitsPixel == 32);
    image.SetSize(bm.bmWidth, bm.bmHeight);
    BITMAPINFO bi;
    memset(&bi, 0, sizeof(bi));
    bi.bmiHeader.biSize = sizeof(BITMAPINFOHEADER);
    bi.bmiHeader.biWidth = bm.bmWidth;
    bi.bmiHeader.biHeight = -bm.bmHeight;
    bi.bmiHeader.biPlanes = 1;
    bi.bmiHeader.biBitCount = 32;
    bi.bmiHeader.biCompression = BI_RGB;
    HDC dc = GetDC(NULL);
    assert(dc != NULL);
    ret = GetDIBits(dc, bitmap, 0, bm.bmHeight, &image(0, 0), &bi, DIB_RGB_COLORS);
    assert(ret);
    ret = ReleaseDC(NULL, dc);
    assert(ret);
}

void GetClientImage(HWND wnd, Image& image)
{
    RECT rc;
    BOOL ret = GetClientRect(wnd, &rc);
    assert(ret);
    int cx = rc.right - rc.left;
    int cy = rc.bottom - rc.top;
    HDC dc = GetDC(wnd);
    assert(dc != NULL);
    HDC backDC = CreateCompatibleDC(dc);
    assert(backDC != NULL);
    HBITMAP bitmap = CreateCompatibleBitmap(dc, cx, cy);
    assert(bitmap != NULL);
    HBITMAP oldBitmap = (HBITMAP)SelectObject(backDC, bitmap);
    ret = BitBlt(backDC, 0, 0, rc.right - rc.left, rc.bottom - rc.top, dc, 0, 0, SRCCOPY);
    assert(ret);
    ret = ReleaseDC(wnd, dc);
    assert(ret);
    bitmap = (HBITMAP)SelectObject(backDC, oldBitmap);
    assert(bitmap != NULL);
    ret = DeleteDC(backDC);
    assert(ret);
    GetImage(bitmap, image);
    ret = DeleteObject(bitmap);
    assert(ret);
}

template<int count>
class ImageCompare
{
public:
    void Init(int id)
    {
        assert(count > 0);
        HMODULE inst = LoadLibrary(_T("winmine.exe")); // GetModuleHandle(NULL);
        assert(inst != NULL);
        HBITMAP bmp = (HBITMAP)LoadImage(inst, MAKEINTRESOURCE(id), IMAGE_BITMAP, 0, 0, 0);
        assert(bmp);
        Image image;
        GetImage(bmp, image);
        BOOL ret = DeleteObject(bmp);
        assert(ret);
        ret = FreeLibrary(inst);
        assert(ret);

        width = image.Width();
        height = image.Height() / count;
        assert(image.Height() % count == 0);
        for (int i = 0; i < count; ++i)
        {
            images[i].Assign(image, 0, height * i, width, height);
        }
    }
    int GetIndex(const Image& image, int x, int y) const
    {
        for (int i = 0; i < count; ++i)
        {
            if (images[i].IsSame(image, x, y))
            {
                return count - 1 - i;
            }
        }
        assert(false); // TODO
        return -1;
    }
    static int GetCount(void) { return count; }
    int Width(void) { return width; }
    int Height(void) { return height; }

private:
    int width, height;
    Image images[count];
};

class MineController
{
public:
    void Init(void)
    {
        cells.Init(410);
        CellWidth = cells.Width();
        CellHeight = cells.Height();
        digits.Init(420);
        DigitWidth = digits.Width();
        DigitHeight = digits.Height();
        faces.Init(430);
        FaceWidth = faces.Width();
        FaceHeight = faces.Height();
    }
    void Update(void)
    {
        isFinished = true;

        Image image;
        GetClientImage(GetMineWindow(), image);
        int FaceLeft = (image.Width() - FaceWidth) / 2 + 2;
        int face = GetFace(image, FaceLeft, FaceTop);
        if (face == FaceDone || face == FaceFail) return;
        GetField(image, field);
        isFinished = IsFinished(field);
        remained = GetNumber(image, RemainLeft, RemainTop);
    }
    static void Reset(void)
    {
        HWND wnd = GetMineWindow();
        PostMessage(wnd, WM_KEYDOWN, VK_F2, 0);
        PostMessage(wnd, WM_KEYUP, VK_F2, 0);
    }
    static void ClickMine(int x, int y, bool left, bool right)
    {
        POINT pt;
        pt.x = LeftBorder + CellWidth * x + CellWidth / 2;
        pt.y = TopBorder + CellHeight * y + CellHeight / 2;
        LPARAM lp = MAKELPARAM(pt.x, pt.y);
        HWND wnd = GetMineWindow();
        BOOL ret = MapWindowPoints(wnd, NULL, &pt, 1);
        assert(ret);
        ret = SetCursorPos(pt.x, pt.y);
        assert(ret);
        WPARAM wp = 0;
        if (left)
        {
            wp |= MK_LBUTTON;
            ret = PostMessage(wnd, WM_LBUTTONDOWN, wp, lp);
            assert(ret);
        }
        if (right)
        {
            wp |= MK_RBUTTON;
            ret = PostMessage(wnd, WM_RBUTTONDOWN, wp, lp);
            assert(ret);
        }
        if (right)
        {
            ret = PostMessage(wnd, WM_RBUTTONUP, wp, lp);
            assert(ret);
            wp &= (~MK_RBUTTON);
        }
        if (left)
        {
            ret = PostMessage(wnd, WM_LBUTTONUP, wp, lp);
            assert(ret);
            wp &= (~MK_LBUTTON);
        }
    }
    bool IsFinished(void) const { return isFinished; }
    const Field& GetField(void) const { return field; }
    int Remained(void) const { return remained; };
private:
    ImageCompare<16> cells;
    ImageCompare<12> digits;
    ImageCompare<5> faces;
    static const int TopBorder = 55;
    static const int LeftBorder = 12;
    static const int RightBorder = 8;
    static const int BottomBorder = 8;
    static const int FaceTop = 16;
    static const int FaceDone = 3;
    static const int FaceFail = 2;
    static const int RemainTop = 16;
    static const int RemainLeft = 17;
    static int CellWidth;
    static int CellHeight;
    static int DigitWidth;
    static int DigitHeight;
    static int FaceWidth;
    static int FaceHeight;
    static bool IsFinished(const Field& field)
    {
        for (int y = 0; y < field.Height(); ++y)
        {
            for (int x = 0; x < field.Width(); ++x)
            {
                CellValue v = field(x, y);
                if (v == CellExploded) return true;
            }
        }
        return false;
    }

    int GetFace(const Image& image, int x, int y) const
    {
        int v = faces.GetIndex(image, x, y);
        assert(v >= 0);
        assert(v < 5);
        if (v == FaceFail || v == FaceDone) return v;
        return 0;
    }
    int GetNumber(const Image& image, int x, int y) const
    {
        bool neg = false;
        int r = 0;
        for (int i = 0; i < 3; ++i)
        {
            int v = digits.GetIndex(image, x + i * DigitWidth, y);
            if (i == 0 && v == 0)
            {
                neg = true;
                continue;
            }
            assert(i <= 10);
            if (i > 9) i = 0;
            r *= 10;
            r += v;
        }
        return r;
    }
    CellValue GetCell(const Image& image, int x, int y) const
    {
        int val = cells.GetIndex(image, x, y);
        if (val < 9) return (CellValue)val;
        if (val == 13) ClickMine(x, y, false, true);
        if (val == 15 || val == 13) return CellUnknown;
        if (val == 14) return CellFlag;
        return CellExploded;
    }

    static HWND GetMineWindow(void)
    {
        TCHAR* MineClass = _T("Minesweeper");
        HWND wnd = FindWindow(MineClass, NULL);
        while (wnd == NULL)
        {
            system("start winmine");
            Sleep(1000);
            wnd = FindWindow(MineClass, NULL);
        }
        BOOL ret = ShowWindow(wnd, SW_SHOW);
        assert(ret);
        return wnd;
    }

    void GetField(const Image& image, Field& field) const
    {
        int hcells = (image.Width() - LeftBorder - RightBorder) / CellWidth;
        int vcells = (image.Height() - TopBorder - BottomBorder) / CellHeight;
        assert(hcells * CellWidth + LeftBorder + RightBorder == image.Width());
        assert(vcells * CellHeight + TopBorder + BottomBorder == image.Height());
        field.SetSize(hcells, vcells);

        for (int i = 0; i < vcells; ++i)
        {
            int y = TopBorder + i * CellHeight;
            for (int j = 0; j < hcells; ++j)
            {
                int x = LeftBorder + j * CellWidth;
                CellValue v = GetCell(image, x, y);
                field(j, i) = v;
            }
        }
    }

    Field field;
    bool isFinished;
    int remained;
};

int MineController::CellWidth;
int MineController::CellHeight;
int MineController::DigitWidth;
int MineController::DigitHeight;
int MineController::FaceWidth;
int MineController::FaceHeight;

class MineSweeper
{
public:
    MineSweeper(MineController& ctlr):controller(ctlr){};

    bool canGuess;
    bool singleStep;
    bool Sweep(void)
    {
        controller.Update();
        if (controller.IsFinished()) return false;
        const Field& field = controller.GetField();
        PartialResults partialResults;
        GetPartialResults(field, partialResults);
        Actions2D actions(field.Width(), field.Height());
        int acts = Induce(partialResults, actions);
        if (acts <= 0 && canGuess) acts = Guess(field, partialResults, controller.Remained(), actions);

        if (acts <= 0) return false;
        ExecuteActions(actions);
        return true;
    }
private:
    const MineSweeper& operator=(const MineSweeper&);

    struct Position
    {
        Position(void):x(0),y(0){}
        Position(int x_, int y_):x(x_),y(y_){}
        int x, y;
    };

    typedef BoundArray<Position, 8> PosArray;
    struct PartialResult
    {
        int x, y;
        int mines;
        PosArray cells;
    };
    typedef vector<PartialResult> PartialResults;

    void GetPartialResults(const Field& field, PartialResults& presults)
    {
        // get cells that contains a determined number of mines
        presults.clear();
        static int off[8][2]={{-1,-1},{0,-1},{1,-1},{-1,0},{1,0},{-1,1},{0,1},{1,1}};
        for (int y = 0; y < field.Height(); ++y)
        {
            for (int x = 0; x < field.Width(); ++x)
            {
                CellValue v = field(x, y);
                if (v > 8 || v <= 0) continue;
                PartialResult pres = {x, y, v};
                for (int i = 0; i < 8; ++i)
                {
                    int x1 = x + off[i][0];
                    if (x1 < 0 || x1 >= field.Width()) continue;
                    int y1 = y + off[i][1];
                    if (y1 < 0 || y1 >= field.Height()) continue;
                    CellValue v1 = field(x1, y1);
                    if (v1 == CellUnknown) pres.cells.add(Position(x1, y1));
                    else if (v1 == CellFlag) --pres.mines;
                }
                assert(pres.mines <= pres.cells.size());
                if (!pres.cells.empty()) presults.push_back(pres);
            }
        }
    }

    static int GetOverlapped(const PosArray& a1, const PosArray& a2,
        bool (&ov1)[8], bool (&ov2)[8])
    {
        int overlaped = 0;
        for (int i = 0; i < a1.size(); ++i)
        {
            for (int j = 0; j < a2.size(); ++j)
            {
                const Position& p1 = a1[i];
                const Position& p2 = a2[j];
                if (p1.x == p2.x && p1.y == p2.y)
                {
                    ov1[i] = true;
                    ov2[j] = true;
                    ++overlaped;
                }
            }
        }
        return overlaped;
    }

    static bool InduceStep(PartialResult& pr1, PartialResult& pr2, PartialResult& pr3)
    {
        // for overlapped two cell groups,
        // if mine count in overlapped cells is determined:
        // - create group for overlapped cells
        // - exclude overlapped from the original 2 groups
        if (abs(pr1.x - pr2.x) > 2) return false;
        if (abs(pr1.y - pr2.y) > 2) return false;
        int pc1 = pr1.cells.size();
        int pc2 = pr2.cells.size();
        bool ov1[8] = {}, ov2[8] = {};
        int overlapedCells = GetOverlapped(pr1.cells, pr2.cells, ov1, ov2);
        if (overlapedCells == 0) return false; // no overlap
        if (overlapedCells == pc1)
        {
            pr2.cells.remove(ov2);
            pr2.mines -= pr1.mines;
            return false;
        }
        if (overlapedCells == pc2)
        {
            pr1.cells.remove(ov1);
            pr1.mines -= pr2.mines;
            return false;
        }
        int minOverlapedMines = max(pr1.mines - (pc1 - overlapedCells), pr2.mines - (pc2 - overlapedCells));
        if (minOverlapedMines < 0) minOverlapedMines = 0;
        int maxOverlapedMines = min(pr1.mines, pr2.mines);
        if (maxOverlapedMines > overlapedCells) maxOverlapedMines = overlapedCells;
        if (minOverlapedMines < maxOverlapedMines) return false;
        pr3.x = pr1.x;
        pr3.y = pr1.y;
        pr3.mines = minOverlapedMines;
        for (int i = 0; i < pc1; ++i)
        {
            if (ov1[i]) pr3.cells.add(pr1.cells[i]);
        }
        pr1.mines -= pr3.mines;
        pr1.cells.remove(ov1);
        pr2.mines -= pr3.mines;
        pr2.cells.remove(ov2);
        return true;
    }

    enum MineAction
    {
        ClickNone, ClickLeft, ClickRight, ClickBoth
    };
    typedef Array2D<MineAction> Actions2D;
    void ClickMine(int x, int y, MineAction act) const
    {
        static bool LeftRight[][2] = {{false,false},{true,false},{false,true},{true,true}};
        controller.ClickMine(x, y, LeftRight[act][0], LeftRight[act][1]);
    }

    static int Induce(PartialResults& presults, Actions2D& actions)
    {
        for (size_t i = 0; i < presults.size(); ++i)
        {
            for (size_t j = i + 1; j < presults.size(); ++j)
            {
                PartialResult& pr1 = presults[i];
                PartialResult& pr2 = presults[j];
                PartialResult pr3 = {};
                if (InduceStep(pr1, pr2, pr3))
                {
                    presults.push_back(pr3);
                }
            }
        }
        reverse(presults.begin(), presults.end());
        for (size_t i = 0; i < presults.size(); ++i)
        {
            for (size_t j = i + 1; j < presults.size(); ++j)
            {
                PartialResult& pr1 = presults[i];
                PartialResult& pr2 = presults[j];
                PartialResult pr3 = {};
                if (InduceStep(pr1, pr2, pr3))
                {
                    presults.push_back(pr3);
                }
            }
        }
        int cnt = 0;
        for (size_t i = 0; i < presults.size(); ++i)
        {
            PartialResult& pr = presults[i];
            MineAction act = ClickNone;
            if (pr.mines == 0) act = ClickLeft;
            else if (pr.mines == pr.cells.size()) act = ClickRight;
            if (act == ClickNone) continue;

            for (int j = 0; j < pr.cells.size(); ++j)
            {
                const Position& p = pr.cells[j];
                actions(p.x, p.y) = act;
                ++cnt;
            }
        }
        return cnt;
    }

    struct PartialResultF
    {
        int x, y;
        float minesPerCell;
        PosArray cells;
    };
    typedef vector<PartialResultF> PartialResultsF;

    static void GuessStep(PartialResultF& pr1, PartialResultF& pr2)
    {
        if (abs(pr1.x - pr2.x) > 2) return;
        if (abs(pr1.y - pr2.y) > 2) return;
        bool ov1[8] = {}, ov2[8] = {};
        int overlapedCells = GetOverlapped(pr1.cells, pr2.cells, ov1, ov2);
        if (overlapedCells == 0) return;
        if (fabs(pr1.minesPerCell - pr2.minesPerCell) < 0.000001) return;
        if (pr1.minesPerCell < pr2.minesPerCell)
        {
            pr1.cells.remove(ov1);
            pr1.minesPerCell -= pr2.minesPerCell * overlapedCells / pr1.cells.size();
        }
        else
        {
            pr2.cells.remove(ov2);
            pr2.minesPerCell -= pr1.minesPerCell * overlapedCells / pr2.cells.size();
        }
    }

    static int Guess(const Field& field, PartialResults& presults, int remained, Actions2D& actions)
    {
        PartialResultsF presultsF;
        presultsF.reserve(presults.size());
        for (size_t i = 0; i < presults.size(); ++i)
        {
            presultsF.resize(presultsF.size() + 1);
            PartialResultF& prf = presultsF.back();
            PartialResult& pr = presults[i];
            prf.x = pr.x;
            prf.y = pr.y;
            prf.minesPerCell = (float)pr.mines / pr.cells.size();
            prf.cells = pr.cells;
        }
        for (size_t i = 0; i < presultsF.size(); ++i)
        {
            for (size_t j = i + 1; j < presultsF.size(); ++j)
            {
                GuessStep(presultsF[i], presultsF[j]);
            }
        }
        Array2D<float> mines(field.Width(), field.Height());

        float insideMines = (float)remained;
        float minMine = 1.0f;
        Position posMin;
        for (size_t i = 0; i < presultsF.size(); ++i)
        {
            const PartialResultF& pr = presultsF[i];
            if (pr.cells.empty()) continue;
            for (int j = 0; j < pr.cells.size(); ++j)
            {
                const Position& pt = pr.cells[j];
                mines(pt.x, pt.y) = pr.minesPerCell;
                insideMines -= pr.minesPerCell;
            }
            if (pr.minesPerCell < minMine) 
            {
                posMin = pr.cells[0];
                minMine = pr.minesPerCell;
            }
        }
        int inside = 0;
        Position firstInside;
        for (int y = 0; y < mines.Height(); ++y)
        {
            for (int x = 0; x < mines.Width(); ++x)
            {
                if (mines(x, y) != 0.0f) continue;
                if (field(x, y) != CellUnknown) continue;
                if (inside == 0) firstInside = Position(x, y);
                ++inside;
            }
        }
        if (inside > 0 && insideMines / inside < minMine)
        {
            minMine = insideMines / inside;
            posMin = firstInside;
        }
        if (minMine < 1.000001f)
        {
            actions(posMin.x, posMin.y) = ClickLeft;
            return 1;
        }
        return 0;
    }

    MineController& controller;
    void ExecuteActions(const Actions2D& actions)
    {
        for (int y = 0; y < actions.Height(); ++y)
        {
            for (int x = 0; x < actions.Width(); ++x)
            {
                MineAction act = actions(x, y);
                if (act == ClickNone) continue;
                ClickMine(x, y, act);
                if (singleStep) return;
            }
        }
        Sleep(1);
    }
};

int main(void)
{
    MineController controller;
    controller.Init();
    MineSweeper sweeper(controller);

    bool shutdown = false;
    while (!shutdown)
    {
        printf("Click\tStep\tReset\tAll\tsaFe\tQuit: ");
        char ch = (char)_getch();
        printf("%c\n", ch);
        switch (ch)
        {
        case 'a':
        case 'A':
            sweeper.singleStep = false;
            sweeper.canGuess = true;
            while (sweeper.Sweep());
            break;
        case 'c':
        case 'C':
            sweeper.singleStep = true;
            sweeper.canGuess = true;
            sweeper.Sweep();
            break;
        case 'f':
        case 'F':
            sweeper.singleStep = false;
            sweeper.canGuess = false;
            while (sweeper.Sweep());
            break;
        case 'r':
        case 'R':
            controller.Reset();
            break;
        case 's':
        case 'S':
            sweeper.singleStep = false;
            sweeper.canGuess = true;
            sweeper.Sweep();
            break;
        default:
            shutdown = true;
        }
    }
    return 0;
}
